// 完全二叉树：除了最底层没有填满，其余层的节点都填满，并且最底层的节点都集中在最左边，最底层，有 1 到 2^k - 1个节点

// 思路1：后序遍历

function countNodes(root) {
    if (!root) {
        return 0
    }
    return countNodes(root.left) + countNodes(root.right) + 1
}

// 思路2：层序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，queue的大小
function countNodes2(root) {
    if (!root) {
        return 0
    }
    let queue = [root]
    let count = 0
    while (queue.length) {
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            count++
            if (node.left) {
                queue.push(node.left)
            }            
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return count
}

// 思路3： 利用满二叉树的特性，简化递归深度
// 时间复杂度：O(logn)，n是二叉树的节点数
// 空间复杂度：O(1), 递归栈的大小
function countNodes3(root) {
    if (!root) {
        return 0
    }
    let leftHeight = 1
    let rightHeight = 1
    let left = root.left
    let right = root.right
    while (left) {
        left = left.left
        leftHeight++
    }
    while (right) {
        right = right.right
        rightHeight++
    }
    if (leftHeight === rightHeight) {
        return 2 ** leftHeight - 1
    }
    return countNodes3(root.left) + countNodes3(root.right) + 1

}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(countNodes(root))
console.log(countNodes2(root))
console.log(countNodes3(root))